package Java_Concurrency_in_Practice.c8_5;

import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;

/**
 * 这种并发方法引入了一种新形式的限制并去掉了一些原有的限制, 新的限制在这个问题域中更合适</br>
 * 串行版本程序执行深度优先搜索, 因此搜索过程中受限于栈的大小.</br>
 * 并发版本的程序执行广度优先搜索, 因此不会受到栈大小的限制</br>
 * 为了找到答案后停止搜索, 需要通过某种方式来检查是否已经有线程找到了一个解答.</br>
 * 这种描述是一种闭锁机制</br>
 * @param <P> position
 * @param <M> move
 */
public class ConcurrentPuzzleSolver<P, M> {
    private final Puzzle<P, M> puzzle;
    private final ExecutorService exec;
    private final ConcurrentHashMap<P, Boolean> seen;
    final ValueLatch<Node<P, M>> solution = new ValueLatch<Node<P, M>>();

    public ConcurrentPuzzleSolver(Puzzle<P, M> puzzle, ExecutorService exec, ConcurrentHashMap<P, Boolean> seen) {
        this.puzzle = puzzle;
        this.exec = exec;
        this.seen = seen;
    }

    public List<M> solve() throws InterruptedException {
        try {
            P p = puzzle.initialPosition();
            exec.execute(newTask(p, null, null));
            // 阻塞直到找到解答
            Node<P, M> solnNode = solution.getValue();
            return (solution == null) ? null : solnNode.asMoveList();
        } finally {
            exec.shutdown();
        }

    }

    protected Runnable newTask(P p, M m, Node<P, M> prev) {
        return new SolverTask(p, m, prev);
    }

    class SolverTask extends Node<P, M> implements Runnable {

        public SolverTask(P pos, M move, Node<P, M> prev) {
            super(pos, move, prev);
        }

        @Override
        public void run() {
            if (solution.isSet() || seen.putIfAbsent(pos, true) != null) {
                return; // 已经找到了解答或者已经遍历了这个位置
            }
            if (puzzle.isGoal(pos)) {
                solution.setValue(this);
            } else {
                for (M m : puzzle.legalMoves(pos)) {
                    exec.execute(newTask(puzzle.move(pos, m), m, this));
                }
            }
        }
    }
}
